package backtrack_or_fs;

import java.util.ArrayList;
import java.util.List;


// 枚举剪枝法 ：对起始下标进行递归遍历    模板 ：bfs(fromIdx) {  if() return; for(int i = fromIdx; i < n; i++){...}}
public class 二进制手表_401 {

            int[] hours = new int[]{1,2,4,8};
            int[] mins = new int[]{1,2,4,8,16,32};
            public List<String> readBinaryWatch(int turnedOn) {
                List<String> res = new ArrayList<>();
                if(turnedOn > 8) return res; // 剪枝点1 ：分钟最大能选5个  小时最多能选3个
                bt(res, turnedOn, 0, 0, 0);
                return res;
            }
            // 避免完全回溯  需要剪枝  
            // 剪枝点2 ： 回溯过的下标不再使用  通过传递fromIdx来完成
            // 剪枝点3 ： 不满足要求的直接return 本题中时间大于11：59的都不满足
            private void bt(List<String> res, int remainder, int fromIdx, int hour, int min) {
                if(hour > 11 || min > 59) return;
                if(remainder == 0){
                   res.add(hour + ":" + ( min < 10? ("0" + min) : min)); 
                   return;
                } 
                // 每个点既可以是小时 也可以是分钟，因此放到一起选择
                // 注意不能回头  这次选i  下次从i+1开始 到10 中间选一个数字，依次往后  
                for(int i = fromIdx; i < 10 ; i++) {
                    if(i < 4) {
                        bt(res, remainder - 1, i + 1, hour + hours[i] ,  min);
                    } else {
                        bt(res, remainder - 1, i + 1, hour, min + mins[i - 4]);
                    }
                }
            }
        }